/*
** 2011 July 9
**
** The author disclaims copyright to this source code. In place of
** a legal notice, here is a blessing:
**
** May you do good and not evil.
** May you find forgiveness for yourself and forgive others.
** May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains code for the Sorter object, used in concert with
** a VdbeCursor to sort large numbers of keys (as may be required, for
** example, by CREATE INDEX statements on tables too large to fit in main
** memory).
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <assert.h>

#define SQLITE_OK           0   /* Successful result */
/* beginning-of-error-codes */
#define SQLITE_ERROR        1   /* SQL error or missing database */
#define SQLITE_NOMEM        2   /* A malloc() failed */
#define SQLITE_IOERR_SHORT_READ 3

#if defined(_MSC_VER) || defined(__BORLANDC__)
typedef __int64 i64;
typedef unsigned __int64 u64;
#else
typedef long long int i64;
typedef unsigned long long int u64;
#endif
typedef unsigned short u16;
typedef unsigned int u32;
typedef unsigned char u8;

typedef struct KeyInfo KeyInfo;
typedef struct Mem Mem;
typedef struct UnpackedRecord UnpackedRecord;
typedef struct SorterFile SorterFile;
typedef struct Sorter Sorter;

struct KeyInfo {
	u8 enc;             /* Text encoding - one of the SQLITE_UTF* values */
	u16 nField;         /* Number of entries in aColl[] */
	u8 *aSortOrder;     /* Sort order for each column.  May be NULL */
};
struct Mem {
	char *z;            /* String or BLOB value */
	i64 i;    /* Integer value used when MEM_Int is set in flags */
	double r;           /* Real value */
	int n;              /* Number of characters in string value, excluding '\0' */
};
struct UnpackedRecord {
	KeyInfo *pKeyInfo;  /* Collation and sort-order information */
	u16 nField;         /* Number of entries in apMem[] */
	u8 flags;           /* Boolean settings.  UNPACKED_... below */
	i64 rowid;          /* Used by UNPACKED_PREFIX_SEARCH */
	Mem *aMem;          /* Values */
};
struct SorterFile {
	FILE *fp;
};

typedef struct SorterIter	SorterIter;
typedef struct SorterRecord	SorterRecord;
typedef struct FileWriter	FileWriter;


/*
** NOTES ON DATA STRUCTURE USED FOR N-WAY MERGES:
**
** As keys are added to the sorter, they are written to disk in a series
** of sorted packed-memory-arrays (PMAs). The size of each PMA is roughly
** the same as the cache-size allowed for temporary databases. In order
** to allow the caller to extract keys from the sorter in sorted order,
** all PMAs currently stored on disk must be merged together. This comment
** describes the data structure used to do so. The structure supports
** merging any number of arrays in a single pass with no redundant comparison
** operations.
**
** The aIter[] array contains an iterator for each of the PMAs being merged.
** An aIter[] iterator either points to a valid key or else is at EOF. For
** the purposes of the paragraphs below, we assume that the array is actually
** N elements in size, where N is the smallest power of 2 greater to or equal
** to the number of iterators being merged. The extra aIter[] elements are
** treated as if they are empty (always at EOF).
**
** The aTree[] array is also N elements in size. The value of N is stored in
** the Sorter.nTree variable.
**
** The final (N/2) elements of aTree[] contain the results of comparing
** pairs of iterator keys together. Element i contains the result of
** comparing aIter[2*i-N] and aIter[2*i-N+1]. Whichever key is smaller, the
** aTree element is set to the index of it.
**
** For the purposes of this comparison, EOF is considered greater than any
** other key value. If the keys are equal (only possible with two EOF
** values), it doesn't matter which index is stored.
**
** The (N/4) elements of aTree[] that preceed the final (N/2) described
** above contains the index of the smallest of each block of 4 iterators.
** And so on. So that aTree[1] contains the index of the iterator that
** currently points to the smallest key value. aTree[0] is unused.
**
** Example:
**
** aIter[0] -> Banana
** aIter[1] -> Feijoa
** aIter[2] -> Elderberry
** aIter[3] -> Currant
** aIter[4] -> Grapefruit
** aIter[5] -> Apple
** aIter[6] -> Durian
** aIter[7] -> EOF
**
** aTree[] = { X, 5 0, 5 0, 3, 5, 6 }
**
** The current element is "Apple" (the value of the key indicated by
** iterator 5). When the Next() operation is invoked, iterator 5 will
** be advanced to the next key in its segment. Say the next key is
** "Eggplant":
**
** aIter[5] -> Eggplant
**
** The contents of aTree[] are updated first by comparing the new iterator
** 5 key to the current key of iterator 4 (still "Grapefruit"). The iterator
** 5 value is still smaller, so aTree[6] is set to 5. And so on up the tree.
** The value of iterator 6 - "Durian" - is now smaller than that of iterator
** 5, so aTree[3] is set to 6. Key 0 is smaller than key 6 (Banana<Durian),
** so the value written into element 1 of the array is 0. As follows:
**
**     aTree[] = { X, 0   0, 6    0, 3, 5, 6 }
**
** In other words, each time we advance to the next sorter element, log2(N)
** key comparison operations are required, where N is the number of segments
** being merged (rounded up to the next power of 2).
*/
struct Sorter {
	i64		iWriteOff;      /* Current write offset within file pTemp1 */
	i64		iReadOff;       /* Current read offset within file pTemp1 */
	int		nInMemory;      /* Current size of pRecord list as PMA */
	int		nTree;          /* Used size of aTree/aIter (power of 2) */
	int		nPMA;           /* Number of PMAs stored in pTemp1 */
	int		mnPmaSize;      /* Minimum PMA size, in bytes */
	int		mxPmaSize;      /* Maximum PMA size, in bytes.  0==no limit */
	SorterIter	*aIter;         /* Array of iterators to merge */
	int		*aTree;         /* Current state of incremental merge */
	SorterFile	*pTemp1;        /* PMA file 1 */
	SorterRecord	*pRecord;       /* Head of in-memory record list */
	UnpackedRecord	*pUnpacked;     /* Used to unpack keys */
};


/*
** The following type is an iterator for a PMA. It caches the current key in
** variables nKey/aKey. If the iterator is at EOF, pFile==0.
*/
struct SorterIter {
	i64		iReadOff;       /* Current read offset */
	i64		iEof;           /* 1 byte past EOF for this iterator */
	int		nAlloc;         /* Bytes of space at aAlloc */
	int		nKey;           /* Number of bytes in key */
	SorterFile	*pFile;         /* File iterator is reading from */
	u8		*aAlloc;        /* Allocated space */
	u8		*aKey;          /* Pointer to current key */
	u8		*aBuffer;       /* Current read buffer */
	int		nBuffer;        /* Size of read buffer in bytes */
};


/*
** An instance of this structure is used to organize the stream of records
** being written to files by the merge-sort code into aligned, page-sized
** blocks.  Doing all I/O in aligned page-sized blocks helps I/O to go
** faster on many operating systems.
*/
struct FileWriter {
	int		eFWErr;         /* Non-zero if in an error state */
	u8		*aBuffer;       /* Pointer to write buffer */
	int		nBuffer;        /* Size of write buffer in bytes */
	int		iBufStart;      /* First byte of buffer to write */
	int		iBufEnd;        /* Last byte of buffer to write */
	i64		iWriteOff;      /* Offset of start of buffer in file */
	SorterFile	*pFile;         /* File to write to */
};


/*
** A structure to store a single record. All in-memory records are connected
** together into a linked list headed at Sorter.pRecord using the
** SorterRecord.pNext pointer.
*/
struct SorterRecord {
	void		*pVal;
	int		nVal;
	SorterRecord	*pNext;
};

int SorterNext(Sorter	*pSorter, int *pbEof);

/* Minimum allowable value for the Sorter.nWorking variable */
#define SORTER_MIN_WORKING 10

/* Maximum number of segments to merge in a single pass. */
#define SORTER_MAX_MERGE_COUNT 16

static int _OsRead(SorterFile *id, void *pBuf, int amt, i64 offset) {
	int rc;
	fseek(id->fp, offset, SEEK_SET);
	rc = fread(pBuf, amt, 1, id->fp);
	return 0;
}
static int _OsWrite(SorterFile *id, const void *pBuf, int amt, i64 offset) {
	int rc;
	fseek(id->fp, offset, SEEK_SET);
	rc = fwrite(pBuf, amt, 1, id->fp);
	return 0;
}

static int _OsCloseFree(SorterFile *pFile) {
	int rc = SQLITE_OK;
	rc = fclose(pFile->fp);
	return rc;
}
static int VarintLen(u64 v) {
	int i = 0;
	do {
		i++;
		v >>= 7;
	} while (v != 0 && i<9);
	return i;
}
static int PutVarint(unsigned char *p, u64 v) {
	int i, j, n;
	u8 buf[10];
	if (v & (((u64)0xff000000) << 32)) {
		p[8] = (u8)v;
		v >>= 8;
		for (i = 7; i >= 0; i--) {
			p[i] = (u8)((v & 0x7f) | 0x80);
			v >>= 7;
		}
		return 9;
	}
	n = 0;
	do {
		buf[n++] = (u8)((v & 0x7f) | 0x80);
		v >>= 7;
	} while (v != 0);
	buf[0] &= 0x7f;
	assert(n <= 9);
	for (i = 0, j = n - 1; j >= 0; j--, i++) {
		p[i] = buf[j];
	}
	return n;
}
/*
** Bitmasks used by sqlite3GetVarint().  These precomputed constants
** are defined here rather than simply putting the constant expressions
** inline in order to work around bugs in the RVT compiler.
**
** SLOT_2_0     A mask for  (0x7f<<14) | 0x7f
**
** SLOT_4_2_0   A mask for  (0x7f<<28) | SLOT_2_0
*/
#define SLOT_2_0     0x001fc07f
#define SLOT_4_2_0   0xf01fc07f
static u8 _GetVarint(const unsigned char *p, u64 *v) {
	u32 a, b, s;

	a = *p;
	/* a: p0 (unmasked) */
	if (!(a & 0x80))
	{
		*v = a;
		return 1;
	}

	p++;
	b = *p;
	/* b: p1 (unmasked) */
	if (!(b & 0x80))
	{
		a &= 0x7f;
		a = a << 7;
		a |= b;
		*v = a;
		return 2;
	}

	/* Verify that constants are precomputed correctly */
	assert(SLOT_2_0 == ((0x7f << 14) | (0x7f)));
	assert(SLOT_4_2_0 == ((0xfU << 28) | (0x7f << 14) | (0x7f)));

	p++;
	a = a << 14;
	a |= *p;
	/* a: p0<<14 | p2 (unmasked) */
	if (!(a & 0x80))
	{
		a &= SLOT_2_0;
		b &= 0x7f;
		b = b << 7;
		a |= b;
		*v = a;
		return 3;
	}

	/* CSE1 from below */
	a &= SLOT_2_0;
	p++;
	b = b << 14;
	b |= *p;
	/* b: p1<<14 | p3 (unmasked) */
	if (!(b & 0x80))
	{
		b &= SLOT_2_0;
		/* moved CSE1 up */
		/* a &= (0x7f<<14)|(0x7f); */
		a = a << 7;
		a |= b;
		*v = a;
		return 4;
	}

	/* a: p0<<14 | p2 (masked) */
	/* b: p1<<14 | p3 (unmasked) */
	/* 1:save off p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
	/* moved CSE1 up */
	/* a &= (0x7f<<14)|(0x7f); */
	b &= SLOT_2_0;
	s = a;
	/* s: p0<<14 | p2 (masked) */

	p++;
	a = a << 14;
	a |= *p;
	/* a: p0<<28 | p2<<14 | p4 (unmasked) */
	if (!(a & 0x80))
	{
		/* we can skip these cause they were (effectively) done above in calc'ing s */
		/* a &= (0x7f<<28)|(0x7f<<14)|(0x7f); */
		/* b &= (0x7f<<14)|(0x7f); */
		b = b << 7;
		a |= b;
		s = s >> 18;
		*v = ((u64)s) << 32 | a;
		return 5;
	}

	/* 2:save off p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
	s = s << 7;
	s |= b;
	/* s: p0<<21 | p1<<14 | p2<<7 | p3 (masked) */

	p++;
	b = b << 14;
	b |= *p;
	/* b: p1<<28 | p3<<14 | p5 (unmasked) */
	if (!(b & 0x80))
	{
		/* we can skip this cause it was (effectively) done above in calc'ing s */
		/* b &= (0x7f<<28)|(0x7f<<14)|(0x7f); */
		a &= SLOT_2_0;
		a = a << 7;
		a |= b;
		s = s >> 18;
		*v = ((u64)s) << 32 | a;
		return 6;
	}

	p++;
	a = a << 14;
	a |= *p;
	/* a: p2<<28 | p4<<14 | p6 (unmasked) */
	if (!(a & 0x80))
	{
		a &= SLOT_4_2_0;
		b &= SLOT_2_0;
		b = b << 7;
		a |= b;
		s = s >> 11;
		*v = ((u64)s) << 32 | a;
		return 7;
	}

	/* CSE2 from below */
	a &= SLOT_2_0;
	p++;
	b = b << 14;
	b |= *p;
	/* b: p3<<28 | p5<<14 | p7 (unmasked) */
	if (!(b & 0x80))
	{
		b &= SLOT_4_2_0;
		/* moved CSE2 up */
		/* a &= (0x7f<<14)|(0x7f); */
		a = a << 7;
		a |= b;
		s = s >> 4;
		*v = ((u64)s) << 32 | a;
		return 8;
	}

	p++;
	a = a << 15;
	a |= *p;
	/* a: p4<<29 | p6<<15 | p8 (unmasked) */

	/* moved CSE2 up */
	/* a &= (0x7f<<29)|(0x7f<<15)|(0xff); */
	b &= SLOT_2_0;
	b = b << 8;
	a |= b;

	s = s << 4;
	b = p[-4];
	b &= 0x7f;
	b = b >> 3;
	s |= b;

	*v = ((u64)s) << 32 | a;

	return 9;
}
/*
** Free all memory belonging to the SorterIter object passed as the second
** argument. All structure fields are set to zero before returning.
*/
static void _SorterIterZero(SorterIter *pIter)
{
	free(pIter->aAlloc);
	free(pIter->aBuffer);
	memset(pIter, 0, sizeof(SorterIter));
}


/*
** Read nByte bytes of data from the stream of data iterated by object p.
** If successful, set *ppOut to point to a buffer containing the data
** and return SQLITE_OK. Otherwise, if an error occurs, return an SQLite
** error code.
**
** The buffer indicated by *ppOut may only be considered valid until the
** next call to this function.
*/
static int _SorterIterRead(
	SorterIter *p,              /* Iterator */
	int nByte,                      /* Bytes of data to read */
	u8 **ppOut                      /* OUT: Pointer to buffer containing data */
	)
{
	int	iBuf;                   /* Offset within buffer to read from */
	int	nAvail;                 /* Bytes of data available in buffer */
	assert(p->aBuffer);


	/* If there is no more data to be read from the buffer, read the next
	** p->nBuffer bytes of data from the file into it. Or, if there are less
	** than p->nBuffer bytes remaining in the PMA, read all remaining data.  */
	iBuf = p->iReadOff % p->nBuffer;
	if (iBuf == 0)
	{
		int	nRead;  /* Bytes to read from disk */
		int	rc;     /* _OsRead() return code */

					/* Determine how many bytes of data to read. */
		if ((p->iEof - p->iReadOff) > (i64)p->nBuffer)
		{
			nRead = p->nBuffer;
		}
		else {
			nRead = (int)(p->iEof - p->iReadOff);
		}
		assert(nRead > 0);

		/* Read data from the file. Return early if an error occurs. */
		rc = _OsRead(p->pFile, p->aBuffer, nRead, p->iReadOff);
		if (rc != 0)
			return(rc);
	}
	nAvail = p->nBuffer - iBuf;

	if (nByte <= nAvail)
	{
		/* The requested data is available in the in-memory buffer. In this
		** case there is no need to make a copy of the data, just return a
		** pointer into the buffer to the caller.  */
		*ppOut = &p->aBuffer[iBuf];
		p->iReadOff += nByte;
	}
	else {
		/* The requested data is not all available in the in-memory buffer.
		** In this case, allocate space at p->aAlloc[] to copy the requested
		** range into. Then return a copy of pointer p->aAlloc to the caller.  */
		int nRem;       /* Bytes remaining to copy */

						/* Extend the p->aAlloc[] allocation if required. */
		if (p->nAlloc < nByte)
		{
			int nNew = p->nAlloc * 2;
			while (nByte > nNew)
				nNew = nNew * 2;
			p->aAlloc = (u8 *)realloc(p->aAlloc, nNew);
			if (!p->aAlloc)
				return(SQLITE_NOMEM);
			p->nAlloc = nNew;
		}


		/* Copy as much data as is available in the buffer into the start of
		** p->aAlloc[].  */
		memcpy(p->aAlloc, &p->aBuffer[iBuf], nAvail);
		p->iReadOff += nAvail;
		nRem = nByte - nAvail;


		/* The following loop copies up to p->nBuffer bytes per iteration into
		** the p->aAlloc[] buffer.  */
		while (nRem > 0)
		{
			int	rc;     /* _SorterIterRead() return code */
			int	nCopy;  /* Number of bytes to copy */
			u8	*aNext; /* Pointer to buffer to copy data from */

			nCopy = nRem;
			if (nRem > p->nBuffer)
				nCopy = p->nBuffer;
			rc = _SorterIterRead(p, nCopy, &aNext);
			if (rc != SQLITE_OK)
				return(rc);
			assert(aNext != p->aAlloc);
			memcpy(&p->aAlloc[nByte - nRem], aNext, nCopy);
			nRem -= nCopy;
		}

		*ppOut = p->aAlloc;
	}

	return(SQLITE_OK);
}


/*
** Read a varint from the stream of data accessed by p. Set *pnOut to
** the value read.
*/
static int _SorterIterVarint(SorterIter *p, u64 *pnOut)
{
	int iBuf;

	iBuf = p->iReadOff % p->nBuffer;
	if (iBuf && (p->nBuffer - iBuf) >= 9)
	{
		p->iReadOff += _GetVarint(&p->aBuffer[iBuf], pnOut);
	}
	else {
		u8	aVarint[16], *a;
		int	i = 0, rc;
		do
		{
			rc = _SorterIterRead(p, 1, &a);
			if (rc)
				return(rc);
			aVarint[(i++) & 0xf] = a[0];
		} while ((a[0] & 0x80) != 0);
		_GetVarint(aVarint, pnOut);
	}

	return(SQLITE_OK);
}


/*
** Advance iterator pIter to the next key in its PMA. Return SQLITE_OK if
** no error occurs, or an SQLite error code if one does.
*/
static int _SorterIterNext(
	SorterIter *pIter           /* Iterator to advance */
	)
{
	int	rc;                     /* Return Code */
	u64	nRec = 0;               /* Size of record in bytes */

	if (pIter->iReadOff >= pIter->iEof)
	{
		/* This is an EOF condition */
		_SorterIterZero(pIter);
		return(SQLITE_OK);
	}

	rc = _SorterIterVarint(pIter, &nRec);
	if (rc == SQLITE_OK)
	{
		pIter->nKey = (int)nRec;
		rc = _SorterIterRead(pIter, (int)nRec, &pIter->aKey);
	}

	return(rc);
}


/*
** Initialize iterator pIter to scan through the PMA stored in file pFile
** starting at offset iStart and ending at offset iEof-1. This function
** leaves the iterator pointing to the first key in the PMA (or EOF if the
** PMA is empty).
*/
static int _SorterIterInit(
	const Sorter *pSorter,      /* Sorter object */
	i64 iStart,                     /* Start offset in pFile */
	SorterIter *pIter,          /* Iterator to populate */
	i64 *pnByte                     /* IN/OUT: Increment this value by PMA size */
	)
{
	int	rc = SQLITE_OK;
	int	nBuf;

	nBuf = 1024;

	assert(pSorter->iWriteOff > iStart);
	assert(pIter->aAlloc == 0);
	assert(pIter->aBuffer == 0);
	pIter->pFile = pSorter->pTemp1;
	pIter->iReadOff = iStart;
	pIter->nAlloc = 128;
	pIter->aAlloc = (u8 *)malloc(pIter->nAlloc);
	pIter->nBuffer = nBuf;
	pIter->aBuffer = (u8 *)malloc(nBuf);

	if (!pIter->aBuffer)
	{
		rc = SQLITE_NOMEM;
	}
	else {
		int iBuf;

		memset(pIter->aAlloc, 0, pIter->nAlloc);
		memset(pIter->aBuffer, 0, nBuf);
		iBuf = iStart % nBuf;
		if (iBuf)
		{
			int nRead = nBuf - iBuf;
			if ((iStart + nRead) > pSorter->iWriteOff)
			{
				nRead = (int)(pSorter->iWriteOff - iStart);
			}
			rc = _OsRead(
				pSorter->pTemp1, &pIter->aBuffer[iBuf], nRead, iStart
				);
			assert(rc != SQLITE_IOERR_SHORT_READ);
		}

		if (rc == SQLITE_OK)
		{
			u64 nByte;  /* Size of PMA in bytes */
			pIter->iEof = pSorter->iWriteOff;
			rc = _SorterIterVarint(pIter, &nByte);
			pIter->iEof = pIter->iReadOff + nByte;
			*pnByte += nByte;
		}
	}

	if (rc == SQLITE_OK)
	{
		rc = _SorterIterNext(pIter);
	}
	return(rc);
}


/*
** Compare key1 (buffer pKey1, size nKey1 bytes) with key2 (buffer pKey2,
** size nKey2 bytes).  Argument pKeyInfo supplies the collation functions
** used by the comparison. If an error occurs, return an SQLite error code.
** Otherwise, return SQLITE_OK and set *pRes to a negative, zero or positive
** value, depending on whether key1 is smaller, equal to or larger than key2.
**
** If the bOmitRowid argument is non-zero, assume both keys end in a rowid
** field. For the purposes of the comparison, ignore it. Also, if bOmitRowid
** is true and key1 contains even a single NULL value, it is considered to
** be less than key2. Even if key2 also contains NULL values.
**
** If pKey2 is passed a NULL pointer, then it is assumed that the pCsr->aSpace
** has been allocated and contains an unpacked record that is used as key2.
*/
static void _SorterCompare(
	const void *pKey1, int nKey1,   /* Left side of comparison */
	const void *pKey2, int nKey2,   /* Right side of comparison */
	int *pRes                       /* OUT: Result of comparison */
	)
{
	int rc, n;

	if (pKey2)
	{
		n = nKey1 < nKey2 ? nKey1 : nKey2;
		rc = memcmp(pKey1, pKey2, n);
		if (rc == 0)
		{
			rc = nKey1 - nKey2;
		}
	}
	else
		rc = 1;
	*pRes = rc;
}


/*
** This function is called to compare two iterator keys when merging
** multiple b-tree segments. Parameter iOut is the index of the aTree[]
** value to recalculate.
*/
static int _SorterDoCompare(Sorter	*pSorter, int iOut)
{
	int		i1;
	int		i2;
	int		iRes;
	SorterIter	*p1;
	SorterIter	*p2;

	assert(iOut < pSorter->nTree && iOut > 0);

	if (iOut >= (pSorter->nTree / 2))
	{
		i1 = (iOut - pSorter->nTree / 2) * 2;
		i2 = i1 + 1;
	}
	else {
		i1 = pSorter->aTree[iOut * 2];
		i2 = pSorter->aTree[iOut * 2 + 1];
	}

	p1 = &pSorter->aIter[i1];
	p2 = &pSorter->aIter[i2];

	if (p1->pFile == 0)
	{
		iRes = i2;
	}
	else if (p2->pFile == 0)
	{
		iRes = i1;
	}
	else {
		int res;
		//assert(pSorter->pUnpacked != 0); /* allocated in _SorterMerge() */
		_SorterCompare(
			p1->aKey, p1->nKey, p2->aKey, p2->nKey, &res
			);
		if (res <= 0)
		{
			iRes = i1;
		}
		else {
			iRes = i2;
		}
	}

	pSorter->aTree[iOut] = iRes;
	return(SQLITE_OK);
}


/*
** Initialize the temporary index cursor just opened as a sorter cursor.
*/
int SorterInit(Sorter	**ppSorter)
{
	Sorter	*pSorter;
	int		pgsz;           /* Page size of main database */
	int		mxCache;        /* Cache size */
	char		*d;             /* Dummy */

	pSorter = *ppSorter = (Sorter	*)malloc(sizeof(Sorter));
	if (pSorter == 0)
	{
		return(SQLITE_NOMEM);
	}

	memset(pSorter, 0, sizeof(Sorter));
	//pSorter->pUnpacked = sqlite3VdbeAllocUnpackedRecord(pCsr->pKeyInfo, 0, 0, &d);
	//if (pSorter->pUnpacked == 0)
	//	return(SQLITE_NOMEM);
	//assert(pSorter->pUnpacked == (UnpackedRecord *)d);

	pgsz = 1024;
	pSorter->mnPmaSize = SORTER_MIN_WORKING * pgsz;
	mxCache = 1;
	if (mxCache < SORTER_MIN_WORKING)
		mxCache = SORTER_MIN_WORKING;
	pSorter->mxPmaSize = mxCache * pgsz;

	return(SQLITE_OK);
}


/*
** Free the list of sorted records starting at pRecord.
*/
static void _SorterRecordFree(SorterRecord *pRecord)
{
	SorterRecord	*p;
	SorterRecord	*pNext;
	for (p = pRecord; p; p = pNext)
	{
		pNext = p->pNext;
		free(p);
	}
}


/*
** Free any cursor components allocated by sqlite3VdbeSorterXXX routines.
*/
void SorterClose(Sorter *pSorter)
{
	if (pSorter)
	{
		if (pSorter->aIter)
		{
			int i;
			for (i = 0; i < pSorter->nTree; i++)
			{
				_SorterIterZero(&pSorter->aIter[i]);
			}
			free(pSorter->aIter);
		}
		if (pSorter->pTemp1)
		{
			_OsCloseFree(pSorter->pTemp1);
		}
		_SorterRecordFree(pSorter->pRecord);
		//free(pSorter->pUnpacked);
		free(pSorter);
	}
}


/*
** Allocate space for a file-handle and open a temporary file. If successful,
** set *ppFile to point to the malloc'd file-handle and return SQLITE_OK.
** Otherwise, set *ppFile to 0 and return an SQLite error code.
*/
static int _SorterOpenTempFile(SorterFile **ppFile)
{
	char filename[100];
	SorterFile *pFile;
	pFile = *ppFile = (SorterFile *)malloc(sizeof(SorterFile));
	sprintf(filename, "%d.dat", rand());
	pFile->fp = fopen(filename, "w+b");
	return 0;
}


/*
** Merge the two sorted lists p1 and p2 into a single list.
** Set *ppOut to the head of the new list.
*/
static void _SorterMerge(
	SorterRecord *p1,               /* First list to merge */
	SorterRecord *p2,               /* Second list to merge */
	SorterRecord **ppOut            /* OUT: Head of merged list */
	)
{
	SorterRecord	*pFinal = 0;
	SorterRecord	**pp = &pFinal;
	void		*pVal2 = p2 ? p2->pVal : 0;

	while (p1 && p2)
	{
		int res;
		_SorterCompare(p1->pVal, p1->nVal, pVal2, p2->nVal, &res);
		if (res <= 0)
		{
			*pp = p1;
			pp = &p1->pNext;
			p1 = p1->pNext;
			//pVal2 = 0;
			pVal2 = p2->pVal;
		}
		else {
			*pp = p2;
			pp = &p2->pNext;
			p2 = p2->pNext;
			if (p2 == 0)
				break;
			pVal2 = p2->pVal;
		}
	}
	*pp = p1 ? p1 : p2;
	*ppOut = pFinal;
}


/*
** Sort the linked list of records headed at pCsr->pRecord. Return SQLITE_OK
** if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if an error
** occurs.
*/
static int _SorterSort(Sorter	*pSorter)
{
	int		i;
	SorterRecord	**aSlot;
	SorterRecord	*p;

	aSlot = (SorterRecord * *)malloc(64 * sizeof(SorterRecord *));
	if (!aSlot)
	{
		return(SQLITE_NOMEM);
	}
	memset(aSlot, 0, 64 * sizeof(SorterRecord *));
	p = pSorter->pRecord;
	while (p)
	{
		SorterRecord *pNext = p->pNext;
		p->pNext = 0;
		for (i = 0; aSlot[i]; i++)
		{
			_SorterMerge(p, aSlot[i], &p);
			aSlot[i] = 0;
		}
		aSlot[i] = p;
		p = pNext;
	}

	p = 0;
	for (i = 0; i < 64; i++)
	{
		_SorterMerge(p, aSlot[i], &p);
	}
	pSorter->pRecord = p;

	free(aSlot);
	return(SQLITE_OK);
}


/*
** Initialize a file-writer object.
*/
static void fileWriterInit(
	SorterFile *pFile,            /* File to write to */
	FileWriter *p,                  /* Object to populate */
	i64 iStart                      /* Offset of pFile to begin writing at */
	)
{
	int nBuf = 1024;

	memset(p, 0, sizeof(FileWriter));
	p->aBuffer = (u8 *)malloc(nBuf);
	if (!p->aBuffer)
	{
		p->eFWErr = SQLITE_NOMEM;
	}
	else {
		memset(p->aBuffer, 0, nBuf);
		p->iBufEnd = p->iBufStart = (iStart % nBuf);
		p->iWriteOff = iStart - p->iBufStart;
		p->nBuffer = nBuf;
		p->pFile = pFile;
	}
}


/*
** Write nData bytes of data to the file-write object. Return SQLITE_OK
** if successful, or an SQLite error code if an error occurs.
*/
static void fileWriterWrite(FileWriter *p, u8 *pData, int nData)
{
	int nRem = nData;
	while (nRem > 0 && p->eFWErr == 0)
	{
		int nCopy = nRem;
		if (nCopy > (p->nBuffer - p->iBufEnd))
		{
			nCopy = p->nBuffer - p->iBufEnd;
		}

		memcpy(&p->aBuffer[p->iBufEnd], &pData[nData - nRem], nCopy);
		p->iBufEnd += nCopy;
		if (p->iBufEnd == p->nBuffer)
		{
			p->eFWErr = _OsWrite(p->pFile,
				&p->aBuffer[p->iBufStart], p->iBufEnd - p->iBufStart,
				p->iWriteOff + p->iBufStart
				);
			p->iBufStart = p->iBufEnd = 0;
			p->iWriteOff += p->nBuffer;
		}
		assert(p->iBufEnd < p->nBuffer);

		nRem -= nCopy;
	}
}


/*
** Flush any buffered data to disk and clean up the file-writer object.
** The results of using the file-writer after this call are undefined.
** Return SQLITE_OK if flushing the buffered data succeeds or is not
** required. Otherwise, return an SQLite error code.
**
** Before returning, set *piEof to the offset immediately following the
** last byte written to the file.
*/
static int fileWriterFinish(FileWriter *p, i64 *piEof)
{
	int rc;
	if (p->eFWErr == 0 && p->aBuffer && p->iBufEnd > p->iBufStart)
	{
		p->eFWErr = _OsWrite(p->pFile,
			&p->aBuffer[p->iBufStart], p->iBufEnd - p->iBufStart,
			p->iWriteOff + p->iBufStart
			);
	}
	*piEof = (p->iWriteOff + p->iBufEnd);
	free(p->aBuffer);
	rc = p->eFWErr;
	memset(p, 0, sizeof(FileWriter));
	return(rc);
}


/*
** Write value iVal encoded as a varint to the file-write object. Return
** SQLITE_OK if successful, or an SQLite error code if an error occurs.
*/
static void fileWriterWriteVarint(FileWriter *p, u64 iVal)
{
	int nByte;
	u8 aByte[10];
	nByte = PutVarint(aByte, iVal);
	fileWriterWrite(p, aByte, nByte);
}


/*
** Write the current contents of the in-memory linked-list to a PMA. Return
** SQLITE_OK if successful, or an SQLite error code otherwise.
**
** The format of a PMA is:
**
**     * A varint. This varint contains the total number of bytes of content
**       in the PMA (not including the varint itself).
**
**     * One or more records packed end-to-end in order of ascending keys.
**       Each record consists of a varint followed by a blob of data (the
**       key). The varint is the number of bytes in the blob of data.
*/
static int _SorterListToPMA(Sorter	*pSorter)
{
	int		rc = SQLITE_OK; /* Return code */
	FileWriter	writer;

	memset(&writer, 0, sizeof(FileWriter));

	if (pSorter->nInMemory == 0)
	{
		assert(pSorter->pRecord == 0);
		return(rc);
	}

	rc = _SorterSort(pSorter);

	/* If the first temporary PMA file has not been opened, open it now. */
	if (rc == SQLITE_OK && pSorter->pTemp1 == 0)
	{
		rc = _SorterOpenTempFile(&pSorter->pTemp1);
		assert(rc != SQLITE_OK || pSorter->pTemp1);
		assert(pSorter->iWriteOff == 0);
		assert(pSorter->nPMA == 0);
	}

	if (rc == SQLITE_OK)
	{
		SorterRecord	*p;
		SorterRecord	*pNext = 0;

		fileWriterInit(pSorter->pTemp1, &writer, pSorter->iWriteOff);
		pSorter->nPMA++;
		fileWriterWriteVarint(&writer, pSorter->nInMemory);
		for (p = pSorter->pRecord; p; p = pNext)
		{
			pNext = p->pNext;
			fileWriterWriteVarint(&writer, p->nVal);
			fileWriterWrite(&writer, (u8 *)p->pVal, p->nVal);
			free(p);
		}
		pSorter->pRecord = p;
		rc = fileWriterFinish(&writer, &pSorter->iWriteOff);
	}

	return(rc);
}


/*
** Add a record to the sorter.
*/
int SorterWrite(
	Sorter	*pSorter,                         /* Sorter cursor */
	Mem *pVal                                       /* Memory cell containing record */
	)
{
	int		rc = SQLITE_OK;    /* Return Code */
	SorterRecord	*pNew;                          /* New list element */

	assert(pSorter);
	pSorter->nInMemory += VarintLen(pVal->n) + pVal->n;

	pNew = (SorterRecord *)malloc(pVal->n + sizeof(SorterRecord));
	if (pNew == 0)
	{
		rc = SQLITE_NOMEM;
	}
	else {
		pNew->pVal = (void *)&pNew[1];
		memcpy(pNew->pVal, pVal->z, pVal->n);
		pNew->nVal = pVal->n;
		pNew->pNext = pSorter->pRecord;
		pSorter->pRecord = pNew;
	}


	/* See if the contents of the sorter should now be written out. They
	** are written out when either of the following are true:
	**
	**   * The total memory allocated for the in-memory list is greater
	**     than (page-size * cache-size), or
	**
	**   * The total memory allocated for the in-memory list is greater
	**     than (page-size * 10) and sqlite3HeapNearlyFull() returns true.
	*/
	if (rc == SQLITE_OK && pSorter->nInMemory > pSorter->mxPmaSize)
	{
#ifdef SQLITE_DEBUG
		i64 nExpect = pSorter->iWriteOff
			+ sqlite3VarintLen(pSorter->nInMemory)
			+ pSorter->nInMemory;
#endif
		rc = _SorterListToPMA(pSorter);
		pSorter->nInMemory = 0;
	}

	return(rc);
}


/*
** Helper function for SorterRewind().
*/
static int _SorterInitMerge(
	Sorter	*pSorter,                         /* Cursor handle for this sorter */
	i64 *pnByte                                     /* Sum of bytes in all opened PMAs */
	)
{
	int		rc = SQLITE_OK;    /* Return code */
	int		i;                              /* Used to iterator through aIter[] */
	i64		nByte = 0;                      /* Total bytes in all opened PMAs */

											/* Initialize the iterators. */
	for (i = 0; i < SORTER_MAX_MERGE_COUNT; i++)
	{
		SorterIter *pIter = &pSorter->aIter[i];
		rc = _SorterIterInit(pSorter, pSorter->iReadOff, pIter, &nByte);
		pSorter->iReadOff = pIter->iEof;
		assert(rc != SQLITE_OK || pSorter->iReadOff <= pSorter->iWriteOff);
		if (rc != SQLITE_OK || pSorter->iReadOff >= pSorter->iWriteOff)
			break;
	}

	/* Initialize the aTree[] array. */
	for (i = pSorter->nTree - 1; rc == SQLITE_OK && i > 0; i--)
	{
		rc = _SorterDoCompare(pSorter, i);
	}

	*pnByte = nByte;
	return(rc);
}


/*
** Once the sorter has been populated, this function is called to prepare
** for iterating through its contents in sorted order.
*/
int SorterRewind(Sorter	*pSorter, int *pbEof)
{
	int		rc;             /* Return code */
	SorterFile	*pTemp2 = 0;    /* Second temp file to use */
	i64		iWrite2 = 0;    /* Write offset for pTemp2 */
	int		nIter;          /* Number of iterators used */
	int		nByte;          /* Bytes of space required for aIter/aTree */
	int		N = 2;          /* Power of 2 >= nIter */

	assert(pSorter);


	/* If no data has been written to disk, then do not do so now. Instead,
	** sort the Sorter.pRecord list. The vdbe layer will read data directly
	** from the in-memory list.  */
	if (pSorter->nPMA == 0)
	{
		*pbEof = !pSorter->pRecord;
		assert(pSorter->aTree == 0);
		return(_SorterSort(pSorter));
	}

	/* Write the current in-memory list to a PMA. */
	rc = _SorterListToPMA(pSorter);
	if (rc != SQLITE_OK)
		return(rc);

	/* Allocate space for aIter[] and aTree[]. */
	nIter = pSorter->nPMA;
	if (nIter > SORTER_MAX_MERGE_COUNT)
		nIter = SORTER_MAX_MERGE_COUNT;
	assert(nIter > 0);
	while (N < nIter)
		N += N;
	nByte = N * (sizeof(int) + sizeof(SorterIter));
	pSorter->aIter = (SorterIter *)malloc(nByte);
	if (!pSorter->aIter)
		return(SQLITE_NOMEM);
	memset(pSorter->aIter, 0, nByte);
	pSorter->aTree = (int *)&pSorter->aIter[N];
	pSorter->nTree = N;

	do
	{
		int iNew;                       /* Index of new, merged, PMA */

		for (iNew = 0;
		rc == SQLITE_OK && iNew * SORTER_MAX_MERGE_COUNT < pSorter->nPMA;
			iNew++
			)
		{
			int		rc2;    /* Return code from fileWriterFinish() */
			FileWriter	writer; /* Object used to write to disk */
			i64		nWrite; /* Number of bytes in new PMA */

			memset(&writer, 0, sizeof(FileWriter));


			/* If there are SORTER_MAX_MERGE_COUNT or less PMAs in file pTemp1,
			** initialize an iterator for each of them and break out of the loop.
			** These iterators will be incrementally merged as the VDBE layer calls
			** SorterNext().
			**
			** Otherwise, if pTemp1 contains more than SORTER_MAX_MERGE_COUNT PMAs,
			** initialize interators for SORTER_MAX_MERGE_COUNT of them. These PMAs
			** are merged into a single PMA that is written to file pTemp2.
			*/
			rc = _SorterInitMerge(pSorter, &nWrite);
			assert(rc != SQLITE_OK || pSorter->aIter[pSorter->aTree[1]].pFile);
			if (rc != SQLITE_OK || pSorter->nPMA <= SORTER_MAX_MERGE_COUNT)
			{
				break;
			}

			/* Open the second temp file, if it is not already open. */
			if (pTemp2 == 0)
			{
				assert(iWrite2 == 0);
				rc = _SorterOpenTempFile(&pTemp2);
			}

			if (rc == SQLITE_OK)
			{
				int bEof = 0;
				fileWriterInit(pTemp2, &writer, iWrite2);
				fileWriterWriteVarint(&writer, nWrite);
				while (rc == SQLITE_OK && bEof == 0)
				{
					SorterIter *pIter = &pSorter->aIter[pSorter->aTree[1]];
					assert(pIter->pFile);

					fileWriterWriteVarint(&writer, pIter->nKey);
					fileWriterWrite(&writer, pIter->aKey, pIter->nKey);
					rc = SorterNext(pSorter, &bEof);
				}
				rc2 = fileWriterFinish(&writer, &iWrite2);
				if (rc == SQLITE_OK)
					rc = rc2;
			}
		}

		if (pSorter->nPMA <= SORTER_MAX_MERGE_COUNT)
		{
			break;
		}
		else {
			SorterFile *pTmp = pSorter->pTemp1;
			pSorter->nPMA = iNew;
			pSorter->pTemp1 = pTemp2;
			pTemp2 = pTmp;
			pSorter->iWriteOff = iWrite2;
			pSorter->iReadOff = 0;
			iWrite2 = 0;
		}
	} while (rc == SQLITE_OK);

	if (pTemp2)
	{
		_OsCloseFree(pTemp2);
	}
	*pbEof = (pSorter->aIter[pSorter->aTree[1]].pFile == 0);
	return(rc);
}


/*
** Advance to the next element in the sorter.
*/
int SorterNext(Sorter	*pSorter, int *pbEof)
{
	int		rc;                             /* Return code */

	if (pSorter->aTree)
	{
		int	iPrev = pSorter->aTree[1];      /* Index of iterator to advance */
		int	i;                              /* Index of aTree[] to recalculate */

		rc = _SorterIterNext(&pSorter->aIter[iPrev]);
		for (i = (pSorter->nTree + iPrev) / 2; rc == SQLITE_OK && i > 0; i = i / 2)
		{
			rc = _SorterDoCompare(pSorter, i);
		}

		*pbEof = (pSorter->aIter[pSorter->aTree[1]].pFile == 0);
	}
	else {
		SorterRecord *pFree = pSorter->pRecord;
		pSorter->pRecord = pFree->pNext;
		pFree->pNext = 0;
		_SorterRecordFree(pFree);
		*pbEof = !pSorter->pRecord;
		rc = SQLITE_OK;
	}
	return(rc);
}


/*
** Return a pointer to a buffer owned by the sorter that contains the
** current key.
*/
static void *_SorterRowkey(
	const Sorter *pSorter,      /* Sorter object */
	int *pnKey                      /* OUT: Size of current key in bytes */
	)
{
	void *pKey;
	if (pSorter->aTree)
	{
		SorterIter *pIter;
		pIter = &pSorter->aIter[pSorter->aTree[1]];
		*pnKey = pIter->nKey;
		pKey = pIter->aKey;
	}
	else {
		*pnKey = pSorter->pRecord->nVal;
		pKey = pSorter->pRecord->pVal;
	}
	return(pKey);
}


/*
** Copy the current sorter key into the memory cell pOut.
*/
int SorterRowkey(const Sorter	*pSorter, Mem *pOut)
{
	void		*pKey; int nKey; /* Sorter key to copy into pOut */

	pKey = _SorterRowkey(pSorter, &nKey);
	/*
	if (nKey > pOut->n)
		pOut = (Mem *)realloc(pOut, nKey);
	if (pOut == NULL)
	{
		return(SQLITE_NOMEM);
	}
	pOut->n = nKey;
	memcpy(pOut->z, pKey, nKey);
	*/
	pOut->n = nKey;
	pOut->z = (char *)pKey;
	return(SQLITE_OK);
}


/*
** Compare the key in memory cell pVal with the key that the sorter cursor
** passed as the first argument currently points to. For the purposes of
** the comparison, ignore the rowid field at the end of each record.
**
** If an error occurs, return an SQLite error code (i.e. SQLITE_NOMEM).
** Otherwise, set *pRes to a negative, zero or positive value if the
** key in pVal is smaller than, equal to or larger than the current sorter
** key.
*/
int SorterCompare(
	const Sorter	*pSorter,                 /* Sorter cursor */
	Mem *pVal,                              /* Value to compare to current sorter key */
	int *pRes                               /* OUT: Result of comparison */
	)
{
	void		*pKey; int nKey;        /* Sorter key to compare pVal with */

	pKey = _SorterRowkey(pSorter, &nKey);
	_SorterCompare(pVal->z, pVal->n, pKey, nKey, pRes);
	return(SQLITE_OK);
}

int main(int argc, char *argv[])
{
	Sorter	*pSorter;
	Mem data;
	int i;
	int bEof;
	char tmp[20];

	SorterInit(&pSorter);
	for (i = 0; i < 10000; i++)
	{
		sprintf(tmp, "%d", rand());
		data.z = tmp;
		data.n = strlen(tmp)+1;
		SorterWrite(pSorter, &data);
	}
	SorterRewind(pSorter, &bEof);
	i = 0;
	while (!bEof)
	{
		SorterRowkey(pSorter, &data);
		printf("%5d:%s\n",++i, data.z);
		SorterNext(pSorter, &bEof);
	}
	getchar();
	SorterRewind(pSorter, &bEof);
	i = 0;
	while (!bEof)
	{
		SorterRowkey(pSorter, &data);
		printf("%5d:%s\n", ++i, data.z);
		SorterNext(pSorter, &bEof);
	}
	getchar();
	return 0;
}
